// SparseLifeView by David Bau
//
// I feel silly even saying this, but please don't charge for this
// module or any modification of it, and please give credit where
// credit is due.
// 
// This code is shamelessly ripped off of Sam Streeper's Life module.
// Here is Sam's original description.
//
// ****
// Life is the classical demonstration of cellular automata.
// It was originally created as a simplisting simulation of the dynamics
// of living communities.  I've always thought these things are pretty
// cool; though the algorithm behind Life is exceedingly simple,
// getting good performance seems to require different hacks for
// the display architecture of every machine.
// ...
// Living cell with < 2 neighbors    -> dies of isolation
// Living cell with 2 or 3 neighbors -> lives
// Living cell with > 3 neighbors    -> dies of overcrowding
// empty cell with 3 neighbors       -> life is created (reproduction)
// ...
// ****
// 
// I've changed several things.  First, the method for computing and
// drawing cells was changed to a sparse algorithm that traverses a
// list of live cells.  This way empty cells are looked at as little
// as possible, which is a big win when the field is mostly empty.
// As a nice side effect, the squares get drawn in a (more or less)
// uniformly random order, which gives a smoother visual effect
// without any left-to-right flickering.
//
// The drawing-buffering code was cleaned up.  Smaller lists of rects
// are used, but one for each color.  No noticable performance hit.
//
// A hack in drawSelf was added to work around the double-refresh
// problem when the screensaver first kicks in. (countDown!=ITERATIONS)
//
// The initLife seeding algorithm was changed.  Now it puts inital
// cells in a small circular patch, leaving the rest of the field
// empty, which is much better for the sparse algorithm.  For big
// windows, the circular patch appears in a random starting place.
//
// Stasis checking was changed.  Now it automatically deduces any
// stasis period (up to the size of the stasis buffer), but it takes
// more generations for stasis to be detected.
//
// The color table was generalized to dish out NXColors, instead of
// just hues.  Cell size was generalized.
//
// The control panel was souped up.  Now the color table can be
// changed by the user.  The cell sizes can be changed.  The panel
// animation appears (slowly) partially obscured by the panel
// controls.  The panel animation can be stepped manually by the
// user. Defaults are saved in the user's defaults database.
// Programming the panel was the hardest part, but the result
// looks pretty nice.  I'm beginning to appreciate IB.
//
// 10/20/93 fixes and improvements: used perform:with:afterDelay to
// credits button remove itself correctly.  Also used the same method
// to do the panel animation in a more polite, lazy way.  Changed
// "step" button to a continuous button.  Fixed the timed panel
// animation so it doesn't draw if the view is gone from the window.
//
// 10/23/93 Changed sizing buttons to a matrix of buttons.  Stop
// timed panel animation if already doing an animation somewhere else
// (window or background) by making sure countDown isn't changing.
//
// 10/27/93 Added LIVEEDGE boundary convention so unseen boundary has
// "nutrients" instead of permanent empty squares.  The result is that
// drifters blow up instead of turning into blocks at the edge.
//
// The rules with LIVEEDGE enabled are:
//    Cell dies if it has <2 or >3 neighbors, counting edge neighbors
//    Cell is born if it has =3 neighbors, not counting edge neighbors
//
// Made it so drawing can go right up to the edge of the window,
// using a random offset when it can't completely fill it. Removed
// unneeded calls to flushColor to avoid NXSetColor calls.
//
// 10/29/93 Added DEEPEDGE, so field can extend beyond the visible screen.
// turned off LIVEEDGE feature.  Fine tuned seeding parameters.
//
// 11/05/93 Changed MINCELLSIZE to 2, which can be obtained by a dwrite
// to SparseLifeCellSize only.  Played with matrix of radio buttons for
// so none are highlighed when cellSize matches none of them (e.g.=2),
// but so that once the user starts selecting them, they go into
// setEmptySelectionEnabled:NO mode.
//
// If you add any neat stuff to this module or derive anything
// interesting from it, I'd be interested to see!
//
// I'll probably be bau@cs.cornell.edu for a while.
//
// David Bau 11/05/93
// 777 South Avenue, Weston, MA 02193



#import <appkit/appkit.h>
#import <defaults/defaults.h>
#import <libc.h>
#import <time.h>
#import <dpsclient/wraps.h>
#import "SparseLifeView.h"
#import "Thinker.h"


/* the kind of Life view that appears in the control panel */
@implementation StaticSparseLifeView

- initLife
{
    int x,y,count;
    /* the field is bigger than the view */
    ncols=MIN((bounds.size.width/cellSize+2+2*DEEPEDGE+10),MAXCOLS);
    nrows=MIN((bounds.size.height/cellSize+2+2*DEEPEDGE+10),MAXROWS);
    xoffset=(bounds.size.width-ncols*cellSize)/2;
    yoffset=(bounds.size.height-nrows*cellSize)/2;

    ifirst = -1;
    for (x=0; x<ncols; x++) {
	for (y=0; y<nrows; y++) {
            if (x==0 || y==0 || x==ncols-1 || y==nrows-1) {
                /* Grid[x+y*MAXCOLS].neighbors=0; will contain nonsense */
                Grid[x+y*MAXCOLS].color=(-2);
            } else {
                Grid[x+y*MAXCOLS].neighbors=0;
                Grid[x+y*MAXCOLS].color=(-1);
            }
	}
    }
    /* use uniform random seeding */
    for (count=ncols*nrows/5; count; count--) {
        x=random()%(ncols-2)+1;
        y=random()%(nrows-2)+1;
        if (Grid[x+y*MAXCOLS].color==(-1)) {
            Grid[x+y*MAXCOLS].color=0;
            Grid[x+y*MAXCOLS].next=ifirst;
            ifirst=x+y*MAXCOLS;
        }
        if (Grid[x+y*MAXCOLS].color<COLORS-1) Grid[x+y*MAXCOLS].color++;
    }

    /* init stasis array */
    for (x=0; x<STATSIZE; x++) stasis[x] = x;
    sindex = 0;
    spass = 0;

    /* don't go for too many generations.  Seems it would be boring. */
    countDown = 1000;

    return self;
}

/* main view can tell panel view what colors to use */
- setYoungColor:(NXColor)yc MediumColor:(NXColor)mc OldColor:(NXColor)oc
{
    youngColor=yc;
    mediumColor=mc;
    oldColor=oc;
    [self computeColors];
    return self;
}

/* main view can tell panel what cell size to use */
- setLifeCellSize:(int)cs;
{
    cellSize=cs;
    [self setupSquareBuffer];
    return self;
}

@end






@implementation SparseLifeView

/* here's where the sparse computation and drawing is done */
- oneStep
{
    int icur, *picur;
    int checksum = 0;

    /* finished */
    if (--countDown < 0)
    {
        [self initLife];
        [self display];
    }

    /* pass one: count up neighbors.  Hope gcc does cse well... */
#ifdef LIVEEDGE
#define CONTRIBUTE_TO_GRID(iadj)         \
    if (Grid[iadj].color==(-1)) {        \
        Grid[iadj].color=0;              \
        Grid[iadj].next=ifirst;          \
        ifirst=iadj;                     \
    } else if (Grid[iadj].color==(-2))   \
        Grid[icur].neighbors++;          \
    Grid[iadj].neighbors++;
#else
#define CONTRIBUTE_TO_GRID(iadj)         \
    if (Grid[iadj].color==(-1)) {        \
        Grid[iadj].color=0;              \
        Grid[iadj].next=ifirst;          \
        ifirst=iadj;                     \
    }                                    \
    Grid[iadj].neighbors++;
#endif
    for (icur=ifirst; icur>=0; icur=Grid[icur].next) {
        /* contribute to the west */
        CONTRIBUTE_TO_GRID(icur-1);
        CONTRIBUTE_TO_GRID(icur-1-MAXCOLS);
        CONTRIBUTE_TO_GRID(icur-MAXCOLS);
        CONTRIBUTE_TO_GRID(icur+1-MAXCOLS);
        CONTRIBUTE_TO_GRID(icur+1);
        CONTRIBUTE_TO_GRID(icur+1+MAXCOLS);
        CONTRIBUTE_TO_GRID(icur+MAXCOLS);
        CONTRIBUTE_TO_GRID(icur-1+MAXCOLS);
    }
#undef CONTRIBUTE_TO_GRID

    /* pass two: redraw and prune */
    picur=&ifirst;
    while (*picur>=0) {
        /* a cell only if 2 neighbors and was a cell, or 3 neighbors */
        if (((Grid[*picur].neighbors==2 && Grid[*picur].color) ||
             Grid[*picur].neighbors==3)) {
            if (Grid[*picur].color<COLORS-1) {
                Grid[*picur].color++;
                [self putSquare:(*picur)%MAXCOLS :(*picur)/MAXCOLS
                      Color: Grid[*picur].color];
            }
            Grid[*picur].neighbors=0;
            checksum+=Grid[*picur].color * *picur;
            picur=&(Grid[*picur].next); /* advance */
        } else {
            if (Grid[*picur].color) {
                [self putSquare:(*picur)%MAXCOLS :(*picur)/MAXCOLS
                          Color: 0];
            }
            Grid[*picur].color=(-1);
            Grid[*picur].neighbors=0;
            *picur=Grid[*picur].next; /* delete from list and advance */
        }
    }

    /* empty anything left in the drawing buffers */
    [self flushSquares];
    
    /* check for termination if things are cycling */
    [self checkStasis:checksum];

    return self;
}


- drawSquares
{
    int icur;

    for (icur=ifirst; icur>=0; icur=Grid[icur].next) {
        [self putSquare:(icur%MAXCOLS):(icur/MAXCOLS)
              Color:Grid[icur].color];
    }
    [self flushSquares];
    return self;
}

- putSquare:(int)x :(int)y Color:(int)color
{
    NXRect *newsquare;
#if DEEPEDGE
    if (y<(1+DEEPEDGE) || y>=nrows-(1+DEEPEDGE) ||
        x<(1+DEEPEDGE) || x>=ncols-(1+DEEPEDGE)) return self;
#endif
    if (squareCount[color]>=SQUAREBLOCK) [self flushColor:color];
    newsquare = squareBuffer[color]+squareCount[color];
    newsquare->origin.x=x*cellSize+xoffset;
    newsquare->origin.y=y*cellSize+yoffset;
    squareCount[color]++;

    return self;
}

- flushColor:(int)color
{
    if (squareCount[color]) {
        NXSetColor(colorTable[color]);
        NXRectFillList(squareBuffer[color],squareCount[color]);
        squareCount[color]=0;
    }
    return self;
}

- flushSquares
{
    int color;
    for (color = 0; color<COLORS; color++) {
        [self flushColor: color];
    }
    return self;
}
        
- drawSelf:(const NXRect *)rects :(int)rectCount
{
    if (!rects || !rectCount) return self;
    PSsetgray(0);
    NXRectFill(rects);
    if (countDown!=ITERATIONS) [self drawSquares];
    return self;
}

- (const char *) windowTitle
{	return "Sparse Life";
}

- setupSquareBuffer
{
    int i,b;
    for (i=0; i<COLORS; i++) {
        squareCount[i]=0;
        for (b=0; b<SQUAREBLOCK; b++) {
            squareBuffer[i][b].origin.x=0;
            squareBuffer[i][b].origin.y=0;
            squareBuffer[i][b].size.width=cellSize;
            squareBuffer[i][b].size.height=cellSize;
        }
    }
    return self;
}    

- initFrame:(const NXRect *)frameRect
{
	[super initFrame:frameRect];
	[self getLifeDefaults];
        [self computeColors];
        srandom(time(NULL));

        [self setupSquareBuffer];
	[self initLife];

	return self;
}

static void ColorToString(NXColor color, char *str)
{
    sprintf(str,"%f %f %f",NXRedComponent(color),
            NXGreenComponent(color),NXBlueComponent(color));
}

static NXColor ColorFromString(const char *str)
{
    NXColor color;
    float r,g,b;
    sscanf(str,"%f %f %f",&r,&g,&b);
    r=(r>=0.0 && r<=1.0 ? r : 1.0);
    g=(g>=0.0 && g<=1.0 ? g : 1.0);
    b=(b>=0.0 && b<=1.0 ? b : 1.0);
    color=NXConvertRGBToColor(r,g,b);
    return color;
}
    
- getLifeDefaults
{
    static NXDefaultsVector SparseLifeDefaults = {
        {"SparseLifeYoungColor", "0.083331 0.000000 1.000000"},
        {"SparseLifeMediumColor","0.916669 1.000000 0.000000"},
        {"SparseLifeOldColor",   "0.400005 0.000000 0.066668"},
        {"SparseLifeCellSize",   "8"},
        {NULL}
    };
    
    NXRegisterDefaults("BackSpace",SparseLifeDefaults);
    youngColor=
      ColorFromString(NXGetDefaultValue("BackSpace","SparseLifeYoungColor"));
    mediumColor=
      ColorFromString(NXGetDefaultValue("BackSpace","SparseLifeMediumColor"));
    oldColor=
      ColorFromString(NXGetDefaultValue("BackSpace","SparseLifeOldColor"));
    sscanf(NXGetDefaultValue("BackSpace","SparseLifeCellSize"),"%d",&cellSize);
    if (cellSize<MINCELLSIZE) cellSize=MINCELLSIZE;
    if (cellSize>MAXCELLSIZE) cellSize=MAXCELLSIZE;

    return self;
}


- sizeTo:(NXCoord)width :(NXCoord)height
{
    [super sizeTo:width :height];
    [self initLife];
    return self;
}

/* clear the field and do some random seeding */
- initLife
{
    int x,y,count,i,xr,yr,xo,yo,xa,ya;

    ncols = MIN((bounds.size.width/cellSize)+2+2*DEEPEDGE,MAXCOLS);
    nrows = MIN((bounds.size.height/cellSize)+2+2*DEEPEDGE,MAXROWS);
    xoffset = random()%(1+(int)(bounds.size.width-
                        (ncols-2-2*DEEPEDGE)*cellSize))-(1+DEEPEDGE)*cellSize;
    yoffset = random()%(1+(int)(bounds.size.height-
                        (nrows-2-2*DEEPEDGE)*cellSize))-(1+DEEPEDGE)*cellSize;

    /* clear the field */
    ifirst = -1; /* empty linked list of live cells */
    for (x=0; x<ncols; x++) {
	for (y=0; y<nrows; y++) {
            if (x==0 || y==0 || x==ncols-1 || y==nrows-1) {
                /* Grid[x+y*MAXCOLS].neighbors=0; will contain nonsense */
                Grid[x+y*MAXCOLS].color=(-2);
            } else {
                Grid[x+y*MAXCOLS].neighbors=0;
                Grid[x+y*MAXCOLS].color=(-1);
            }
	}
    }

    /* do some seeding */
    if ((ncols-2)>128) {xr=16+1; xo=1+random()%((ncols-3)-128+1); xa=1;}
    else {xr=((ncols-3)/8)+1; xo=1; xa=((ncols-3)%8)+1;}
    if ((nrows-2)>128) {yr=16+1; yo=1+random()%((nrows-3)-128+1); ya=1;}
    else {yr=((nrows-3)/8)+1; yo=1; ya=((nrows-3)%8)+1;}
    for (count=MAX(xr*yr*4,100); count; count--) {
        /* add up 8 rolls of dice for each coordinate (near gaussian dist) */
        for (i=0, x=xo+random()%xa; i<8; i++) x+=random()%xr;
        for (i=0, y=yo+random()%ya; i<8; i++) y+=random()%yr;
        if (Grid[x+y*MAXCOLS].color==(-1)) {
            Grid[x+y*MAXCOLS].color=0;
            Grid[x+y*MAXCOLS].next = ifirst;
            ifirst=x+y*MAXCOLS;
        }
        if (Grid[x+y*MAXCOLS].color<COLORS-1) Grid[x+y*MAXCOLS].color++;
    }
    
    /* init stasis array */
    for (x=0; x<STATSIZE; x++) stasis[x] = x;
    strack = 0;
    sindex = 0;
    spass = 0;
    countDown = ITERATIONS;

    return self;
}

/* check for stasis (any period of repetition up to STATSIZE) */
- checkStasis:(int)checksum
{
    int i;
    if (!strack || stasis[(sindex+STATSIZE-strack)%STATSIZE]!=checksum) {
        spass=0;
        strack=0;
        for (i=0; i<STATSIZE; i+=STATIVAL) {
            if (stasis[i]==checksum) {
                if (i==sindex) strack=STATSIZE;
                else strack=(sindex+STATSIZE-i)%STATSIZE;
                break;
            }
        }
    } else {
        spass++;
        if (spass>=STATIVAL) countDown=0; /* must match STATIVAL generations */
                                          /* STATIVAL should be more than 2 */
    }

    stasis[sindex++] = checksum;
    if (sindex>=STATSIZE) sindex = 0;
    return self;
}

/* given old-cell color, young-cell color, and medium-cell color, */
/* linearly interpolate the whole color table in HSB space */
- computeColors
{
    float yhue, ysat, ybri;
    float mhue, msat, mbri;
    float ohue, osat, obri;
    float chue;
    int i;

    NXConvertColorToHSB(youngColor, &yhue, &ysat, &ybri);
    NXConvertColorToHSB(mediumColor, &mhue, &msat, &mbri);
    NXConvertColorToHSB(oldColor, &ohue, &osat, &obri);

    /* hue space is circular, so decide which direction to go */
    /* (take the shortest path out of the two possible) */
    if (yhue>mhue && yhue-mhue>0.5) yhue -= 1.0;
    else if (mhue>yhue && mhue-yhue>0.5) yhue += 1.0;
    if (ohue>mhue && ohue-mhue>0.5) ohue -= 1.0;
    else if (mhue>ohue && mhue-ohue>0.5) ohue += 1.0;

    colorTable[0]=NXConvertGrayToColor(NX_BLACK);
    /* interpolate from young to medium */
    for (i=1; i<COLORS/3; i++) {
        chue=(float)(yhue*(COLORS/3-i)+mhue*(i-1))/(COLORS/3-1);
        if (chue<0.0) chue += 1.0;
        else if (chue>1.0) chue -= 1.0;
        colorTable[i]=NXConvertHSBToColor(chue,
            (float)(ysat*(COLORS/3-i)+msat*(i-1))/(COLORS/3-1),
            (float)(ybri*(COLORS/3-i)+mbri*(i-1))/(COLORS/3-1));
    }
    /* from medium to old */
    for (i=COLORS/3; i<COLORS; i++) {
        chue=(float)(mhue*(COLORS-1-i)+ohue*(i-COLORS/3))/(COLORS-1-COLORS/3);
        if (chue<0.0) chue += 1.0;
        else if (chue>1.0) chue -= 1.0;
        colorTable[i]=NXConvertHSBToColor(chue,
            (float)(msat*(COLORS-1-i)+osat*(i-COLORS/3))/(COLORS-1-COLORS/3),
            (float)(mbri*(COLORS-1-i)+obri*(i-COLORS/3))/(COLORS-1-COLORS/3));
    }

    /* pass colors on to panel also, if needed */
    if (panelLifeView && sharedInspectorPanel) {
        [panelLifeView setYoungColor:youngColor
                       MediumColor:mediumColor
                       OldColor:oldColor];
    }

    return self;
}

/* quick update called when color has been changed */
- updateViews
{
    /* update the panel view, if needed */
    if (sharedInspectorPanel) [sharedInspectorPanel display];

    /* update myself */
    [self lockFocus];
    [self drawSquares];
    [self unlockFocus];
    return self;
}

- inspector:sender
{
    char buf[MAXPATHLEN];
    if (!sharedInspectorPanel) {
        sprintf(buf,"%s/SparseLife.nib",[sender moduleDirectory:"SparseLife"]);
        [NXApp loadNibFile:buf owner:self withNames:NO];
        /* initialize some of the panel objects... */
        if (panelYoungColorWell) [panelYoungColorWell setColor:youngColor];
        if (panelMediumColorWell) [panelMediumColorWell setColor:mediumColor];
        if (panelOldColorWell) [panelOldColorWell setColor:oldColor];
        if (panelSizeMatrix) {
            [panelSizeMatrix setEmptySelectionEnabled:YES];
            if (![panelSizeMatrix selectCellWithTag:cellSize]) {
                [panelSizeMatrix selectCellAt:-1:-1];
            } else {
                [panelSizeMatrix setEmptySelectionEnabled:NO];
            }
        }
        if (panelStepButton) {
            [panelStepButton sendActionOn:NX_MOUSEDOWNMASK];
            [panelStepButton setContinuous:YES];
            [panelStepButton setPeriodicDelay:PANELTIME/1000.0
                             andInterval:PANELTIME/1000.0];
        }
        [self computeColors]; /* updates color table inside panelLifeView */
    }
    return sharedInspectorPanel;
}

- inspectorInstalled
{
    int i;
    [self hideCredits:self];
    if (sharedInspectorPanel) [sharedInspectorPanel display];
    if (panelLifeView && sharedInspectorPanel) {
        installedCountDown=countDown;
        for (i=1; i<=5; i++) {
            [self perform:@selector(doSingleStep:) with:self
                  afterDelay:PANELTIME*i cancelPrevious:(i==1)];
        }
    }
    return self;
}

- takeYoungColorFrom:sender
{
    char str[80];
    youngColor=[(NXColorWell *)sender color];
    [self computeColors];
    [self updateViews];
    ColorToString(youngColor,str);
    NXWriteDefault("BackSpace","SparseLifeYoungColor",str);
    return self;
}

- takeMediumColorFrom:sender
{
    char str[80];
    mediumColor=[(NXColorWell *)sender color];
    [self computeColors];
    [self updateViews];
    ColorToString(mediumColor,str);
    NXWriteDefault("BackSpace","SparseLifeMediumColor",str);
    return self;
}

- takeOldColorFrom:sender
{
    char str[80];
    oldColor=[(NXColorWell *)sender color];
    [self computeColors];
    [self updateViews];
    ColorToString(oldColor,str);
    NXWriteDefault("BackSpace","SparseLifeOldColor",str);
    return self;
}

- doSizeMatrix:sender
{
    char str[80];
    int newSize;
    id selected;
    selected=[sender selectedCell];
    if (selected) newSize=[selected tag];
    if (!selected || cellSize==newSize ||
        newSize<MINCELLSIZE || newSize>MAXCELLSIZE) {
        if (![panelSizeMatrix selectCellWithTag:cellSize]) {
            [panelSizeMatrix selectCellAt:-1:-1];
        }
        return self;
    }
    if ([sender isEmptySelectionEnabled]) [sender setEmptySelectionEnabled:NO];
    cellSize=newSize;
    sprintf(str,"%d",cellSize);
    NXWriteDefault("BackSpace","SparseLifeCellSize",str);
    [self setupSquareBuffer];
    [self initLife];
    [self display];
    if (panelLifeView) {
        [panelLifeView setLifeCellSize:cellSize];
        [panelLifeView initLife];
    }
    if (sharedInspectorPanel) [sharedInspectorPanel display];
    return self;
}

- doSingleStep:sender
{
    /* don't animate panel if animating another window */
    if (sender==self && installedCountDown!=countDown) return self;

    /* should not do the panel animation if the view is not loaded or */
    /* if it has been removed from the inspector window */
    if (panelLifeView && sharedInspectorPanel &&
        [panelLifeView canDraw] && [sharedInspectorPanel canDraw]) {
        [panelLifeView lockFocus];
        [panelLifeView oneStep];
        [panelLifeView unlockFocus];
        [sharedInspectorPanel display];
    }
    return self;
}

- doRestart:sender
{
    if (panelLifeView) [panelLifeView initLife];
    if (sharedInspectorPanel) [sharedInspectorPanel display];
    return self;
}


- showCredits:sender
{
    if (panelCreditsView && sharedInspectorPanel) {
        if ([panelCreditsView isDescendantOf:sharedInspectorPanel]) {
            [panelCreditsView removeFromSuperview];
        }
        [sharedInspectorPanel addSubview:panelCreditsView];
        [sharedInspectorPanel display];
    }
    return self;
}

- hideCredits:sender
{
    if (panelCreditsView && sharedInspectorPanel) {
        if ([panelCreditsView isDescendantOf:sharedInspectorPanel]) {
            [panelCreditsView removeFromSuperview];
        }
        [sharedInspectorPanel display];
    }
    return self;
}

/* these methods are needed because we should not rearrange the view */
/* hierarchy while a button is active; we queue the rearranging to be */
/* done later as an event, when nothing is locked on the view */

- doShowCredits:sender
{
    [self perform:@selector(showCredits:)
          with:self afterDelay:0 cancelPrevious:YES];
    return self;
}

- doHideCredits:sender
{
    [self perform:@selector(hideCredits:)
          with:self afterDelay:0 cancelPrevious:YES];
    return self;
}

@end


